\subsubsection{红黑树}
\tikzset{
    treenode/.style = {align=center, inner sep=0pt, text centered,
            font=\sffamily},
    arr_b/.style = {treenode, circle, white, font=\sffamily\bfseries, draw=black,
            fill=black, text width=1.5em},% arbre rouge noir, noeud noir
    arr_r/.style = {treenode, circle, red, draw=red,
            text width=1.5em, very thick},% arbre rouge noir, noeud rouge
    arr_n/.style = {treenode, rectangle, draw=black,
            minimum width=0.5em, minimum height=0.5em}% arbre rouge noir, nil
}


红黑树的特征：
\begin{enumerate}
    \item 节点为红色或者黑色。
    \item 根节点是黑色。
    \item 每个叶子节点都是黑色的空节点（nullptr）。
    \item 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
    \item 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
\end{enumerate}
\begingroup
\endgroup
% \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
%   level distance = 1.5cm}] 
% \node [arr_b] {13}
% child{ node [arr_r] {8} 
%         child{ node [arr_b] {1} 
%             child{ node [arr_r] {5} edge from parent node[above left]
%                      {$x$}} %for a named pointer
%             child{ node [arr_n] {}}
%         }
%         child{ node [arr_b] {20}
%             child{ node [arr_r] {18}}
%             child{ node [arr_n] {}}
%         }                            
%       }
% child{ node [arr_r] {17}
%         child{ node [arr_b] {38} 
%             child{ node [arr_r] {36}}
%             child{ node [arr_r] {39}}
%         }
%         child{ node [arr_b] {51}
%             child{ node [arr_r] {49}
%             child{ node [arr_n] {}}
%         }
% };
% \end{tikzpicture}
红黑树的时间复杂度为O(logn)。
\begin{theorem}
    一棵含有n个节点的红黑树的高度至多为2log(n+1)
\end{theorem}
"一棵含有n个节点的红黑树的高度至多为$2log(n+1)$" 的逆否命题是 "高度为h的红黑树，它的包含的内节点个数至少为 $2^h/2-1$个"。我们只需要证明逆否命题，即可证明原命题为真；即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明：
\begin{itemize}
    \item[第1点]：根据红黑树的"特性(5) ，即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！
    \item[第2点]：根据红黑色的"特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的"可知，从节点x出发达到叶节点"所经历的黑节点数目"$\geq$ "所经历的红节点的数目"。假设x是根节点，则可以得出结论"$bh(x) \leq h/2$"。进而，我们只需证明 "高度为h的红黑树，它的包含的黑节点个数至少为 $2bh(x)-1$个"即可。到这里，我们将需要证明的定理已经由:
\end{itemize}
"一棵含有n个节点的红黑树的高度至多为2log(n+1)"
转变成只需要证明

"高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。


下面通过"数学归纳法"开始论证高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。
\begin{enumerate}
    \item 当树的高度h=0时，
          内节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。
    \item 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的！
\end{enumerate}
下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2bh(x)-1”。当树的高度为 h 时，对于节点x(x为根节点)，其黑高度为$bh(x)$。对于节点x的左右子树，它们黑高度为 $bh(x)$ 或者 $bh(x)-1$。根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 $2bh(x)-1-1$ 个"；所以，节点x所包含的节点至少为 $( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1$。即节点$x$所包含的节点至少为 $2bh(x)-1$。因此，原命题成立。由(1)、(2)得出，"高度为h的红黑树，它的包含的内节点个数至少为 $2^bh(x)-1$个"。因此，“一棵含有n个节点的红黑树的高度至多为$2\log(n+1)$”。
往红黑树插入节点14\figref{fig:rb_insert1}：
\begingroup
\begin{figure}[!htbp]
    \begin{center}
        \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                        level distance = 1.5cm}]
            \node [arr_b] {13}
            child{ node [arr_r] {8}
                    child{ node [arr_b] {1}
                            child{node [arr_n] {}}
                            child{node [arr_r] {6}
                                    child{node [arr_n]{}}
                                    child{node [arr_n]{}}
                                }
                        }
                    child{ node [arr_b] {11}
                            child{ node [arr_n] {}}
                            child{ node [arr_n] {}}
                        }
                }
            child{ node [arr_r] {17}
                    child{ node [arr_b] {15}
                            child{ node [arr_r]{14}
                                    child{node [arr_n]{}}
                                    child{node [arr_n]{}}
                                }
                            child{ node [arr_n]{}}
                        }
                    child{ node [arr_b] {25}
                            child{ node [arr_r] {22}
                                    child{node [arr_n]{}}
                                    child{node [arr_n]{}}
                                }
                            child{ node [arr_r] {27}
                                    child{node[arr_n]{}}
                                    child{node[arr_n]{}}
                                }
                        }
                };
        \end{tikzpicture}
        \caption{插入节点14}
        \label{fig:rb_insert1}
    \end{center}
\end{figure}
\endgroup
向红黑树插入节点21如\figref{fig:rb_insert2},这时候破坏了红黑树规则4。
\begin{figure}[!htbp]
    \centering

    \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                    level distance = 1.5cm}]
        \node [arr_b] {13}
        child{ node [arr_r] {8}
                child{ node [arr_b] {1}
                        child{node [arr_n] {}}
                        child{node [arr_r] {6}
                                child{node [arr_n]{}}
                                child{node [arr_n]{}}
                            }
                    }
                child{ node [arr_b] {11}
                        child{ node [arr_n] {}}
                        child{ node [arr_n] {}}
                    }
            }
        child{ node [arr_r] {17}
                child{ node [arr_b] {15}
                        child{ node [arr_n] {}}
                        child{node [arr_n]{}}
                    }
                child{ node [arr_b] {25}
                        child{ node [arr_r] {22}
                                child{node [arr_r]{21}
                                        child{node [arr_n]{}}
                                        child{node [arr_n]{}}
                                    }
                                child{node [arr_n]{}}
                            }
                        child{ node [arr_r] {27}
                                child{node[arr_n]{}}
                                child{node[arr_n]{}}
                            }
                    }
            };
    \end{tikzpicture}
    \caption{插入节点21}
    \label{fig:rb_insert2}
\end{figure}
为了让红黑树依然符合之前的要求，我们可以将红黑树的红色节点变成黑色节点或者反之以满足红黑树定义。比如可以按照如\figref{fig:rb_change}
\begin{figure}[H]
    \centering

    \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                    level distance = 1.5cm}]
        \node [arr_r] {13}
        child{ node [arr_b] {8}
                child{ node [arr_r] {1}
                        child{node [arr_n] {}}
                        child{node [arr_b] {6}
                                child{node [arr_n]{}}
                                child{node [arr_n]{}}
                            }
                    }
                child{ node [arr_r] {11}
                        child{ node [arr_n] {}}
                        child{ node [arr_n] {}}
                    }
            }
        child{ node [arr_b] {17}
                child{ node [arr_r] {15}
                        child{ node [arr_n] {}}
                        child{node [arr_n]{}}
                    }
                child{ node [arr_r] {25}
                        child{ node [arr_b] {22}
                                child{node [arr_r]{21}
                                        child{node [arr_n]{}}
                                        child{node [arr_n]{}}
                                    }
                                child{node [arr_n]{}}
                            }
                        child{ node [arr_b] {27}
                                child{node[arr_n]{}}
                                child{node[arr_n]{}}
                            }
                    }
            };
    \end{tikzpicture}
    \caption{变色（会引起连锁反应）}
    \label{fig:rb_change}
\end{figure}
左旋也能让不符合规则的红黑树符合规则。左旋如图
% \begin{figure}[htbp]
%     \subfigure[name of the subfigure]{ %第一张子图
%     \begin{minipage}[b]{0.45\linewidth}
%     \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
%         level distance = 1.5cm}] 
%       \node [arr_r] {25}
%       child{ node [arr_b] {22} 
%         child{ node [arr_r] {21}
%                  child{node [arr_n] {}}
%                  child{node [arr_n] {}
%               }
%               }
%               child{ node [arr_n] {}
%           }
%       }
%       child{ node [arr_r] {27}
%           child{node [arr_n]{}}
%           child{node [arr_n]{}}
%       };
%     \end{tikzpicture}
%     \end{minipage}
%     }
%     \subfigure[name of the subfigure]{ %第二张子图
%     \begin{minipage}[b]{0.25\linewidth}
%     \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
%         level distance = 1.5cm}] 
%       \node [arr_r] {25}
%       child{ node [arr_b] {22} 
%         child{ node [arr_r] {21}
%                  child{node [arr_n] {}}
%                  child{node [arr_n] {}
%               }
%               }
%               child{ node [arr_n] {}
%           }
%       }
%       child{ node [arr_r] {27}
%           child{node [arr_n]{}}
%           child{node [arr_n]{}}
%       };
%     \end{tikzpicture}
%     \end{minipage}
%     }
%     \caption{name of the figure} % %大图名称
%     \label{fig:1} %图片引用标记
%     \end{figure}
% \begin{figure}[!htbp]
%     \subfigure[width=0.45\textwidth]{
% \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
%     level distance = 1.5cm}] 
%   \node [arr_r] {25}
%   child{ node [arr_b] {22} 
%     child{ node [arr_r] {21}
%              child{node [arr_n] {}}
%              child{node [arr_n] {}
%           }
%           }
%           child{ node [arr_n] {}
%       }
%   }
%   child{ node [arr_r] {27}
%       child{node [arr_n]{}}
%       child{node [arr_n]{}}
%   };
% \end{tikzpicture}}
% \\
% \subfigure[width=0.45\textwidth]{
%     \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
%         level distance = 1.5cm}] 
%       \node [arr_r] {25}
%       child{ node [arr_b] {22} 
%         child{ node [arr_r] {21}
%                  child{node [arr_n] {}}
%                  child{node [arr_n] {}
%               }
%               }
%               child{ node [arr_n] {}
%           }
%       }
%       child{ node [arr_r] {27}
%           child{node [arr_n]{}}
%           child{node [arr_n]{}}
%       };
%     \end{tikzpicture}
% }


% \end{figure}
\begin{figure}
    \centering
    \subfigure[原树的一部分]{
        \label{fig:subfig:a} %% label for first subfigure 
        \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                        level distance = 1.5cm}]
            \node [arr_r] {25}
            child{ node [arr_b] {22}
                    child{ node [arr_r] {21}
                            child{node [arr_n] {}}
                            child{node [arr_n] {}
                                }
                        }
                    child{ node [arr_n] {}
                        }
                }
            child{ node [arr_r] {27}
                    child{node [arr_n]{}}
                    child{node [arr_n]{}}
                };
        \end{tikzpicture}}
    \hspace{1in}
    \subfigure[左旋]{
        \label{fig:subfig:b} %% label for second subfigure 
        \begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
                        level distance = 1.5cm}]
            \node [arr_r] {25}
            child{ node [arr_b] {22}
                    child{ node [arr_r] {21}
                            child{node [arr_n] {}}
                            child{node [arr_n] {}
                                }
                        }
                    child{ node [arr_n] {}
                        }
                }
            child{ node [arr_r] {27}
                    child{node [arr_n]{}}
                    child{node [arr_n]{}}
                };
        \end{tikzpicture}}
    \caption{左旋操作}
    \label{fig:subfig} %% label for entire figure 
\end{figure}